#include <iostream>
#include <bitset>
using namespace std;

bitset<8> occupy;
int count = 0;
void printResult(int *arr)
{
	int i;
	for (i = 0; i < 8; ++i)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	++count;
}

bool isCandidate(int *arr, int step)
{
	int i;
	int current = arr[step];
	for (i = 0; i < step; ++i)
	{
		int leftDag = current - i - 1;
		int rightDag = current + i + 1;
		int temp = arr[step - i - 1];
		if(leftDag >= 0 && leftDag == temp)
			return false;
		if(rightDag <= 7 && rightDag == temp)
			return false;
	}
	return true;
}

void backtracing(int *arr, int step)
{
	int i;
	if( step == 8 ) 
	{
		printResult(arr);
		return;
	}
	for (i = 0; i < 8; ++i)
	{
		if (occupy[i])
			continue;
		occupy[i] = 1;
		arr[step] = i;
		if(isCandidate(arr, step))
			backtracing(arr, step + 1);
		arr[step] = 0;
		occupy[i] = 0;
	}
}
int main(int argc, char *argv[])
{
	int arr[8];
	backtracing(arr, 0);
	cout << "The number of solution is " << count <<endl;
	return 0;
}
